package LearnAlgorithm.d_标准查找算法and标准排序算法;


public class b1冒泡排序 {
	public static void main(String[] args) {
		int[] arr1 = new int[] {9,8,7,4,5,6,3,2,1};
		BubbleSort(arr1);
		for (int i = 0; i < arr1.length; i++) {
			System.out.print(arr1[i] + " ");
		}
	}

	private static void BubbleSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			/*
			 * 当i=0,(i+1)=1
			 * 一种理解的思想是：代表内循环结束后数组宏观上会有一个值被排好序
			 * 
			 */
			for (int j = 0; j < arr.length-(i+1); j++) {//(i+1)表示在这个内循环中，数组arr已经有(i+1)个值是已经排好序的
				if (arr[j] > arr[j+1]) {
					int tmp = arr[j];
				    arr[j] = arr[j+1];
				    arr[j+1] = tmp;
				}
			}
		}
	}
	
	/**
	 * O(N^2)
	 * @param arr
	 */
	private static void BubbleSort_up(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			boolean ordered = true;
			for (int j = 0; j < arr.length-(i+1); j++) {
				if (arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
					ordered = false;//如果再一次内循环中，没有发生一次值交换，那么就代表数组已经排好序
				}
			}
			if (ordered) {//此时就不再需要接着继续外循环了。所以这里直接break，节省资源
				break;
			}
		}
	}
}
